/******************************************************************************
 * hash.c
 * 
 * Connection hash table.
 * 
 * Copyright (c) 1999-2000, K A Fraser
 * 
 * $Id: hash.c,v 1.1.1.1 2003/01/14 00:30:55 root Exp $
 */

/******************************************************************************
 * WARNING---- BROKEN CODE!!!
 *
 * Ripped out the locking from here one day, not realising the races I was
 * introducing... eg. two insertions can race to update a bucket head ptr,
 * and nastiest of all is when deleting an entry when someone has just
 * looked up that entry but has yet to lock it :-((
 *
 * Non-preemptive threading (eg. Gnu pth) will sort out a lot of this...
 *
 * 3/10/99 - changed to Gnu pth library. This code is now thread-safe. Only
 *  exception is:
 *     Thread 1               Thread 2
 *     --------               --------
 *    element_for_key()
 *                           mutex_lock() ; DESTROY()
 *    mutex_lock() <--- ERROR!!!
 */

#include <stdlib.h>
#include "defines.h"
#include "libusernet.h" 
#include "thread.h"
#include "hash.h"
#include "debug.h"

#ifdef USE_PTH
extern pthread_mutex_t global_poll_mutex;
#else
extern int global_poll_mutex; 
#endif 

#undef FALSE
#undef TRUE
typedef enum { FALSE, TRUE } bool;

struct open_hash_element_t
{
    struct open_hash_element_t *next_in_bucket;
    hash_key_t                  key;
    hash_entry_t                entry;
};

struct open_hash_table_t
{
    int                          size;
    struct open_hash_element_t **elements;
};

#define hash(t, k) ( (k) % ((t)->size) )

hash_table_t init_hash_table(int size)
{
    struct open_hash_table_t *table;
    int                      i;

    /* Allocate and initialise table. */
    if ( !(table = malloc(sizeof(struct open_hash_table_t))) ) return(NULL);
    memset(table, 0, sizeof(struct open_hash_table_t));

    /* Allocate resources for table. */
    if ( (table->elements = malloc(size * sizeof(void *))) == NULL )
    {
        free(table);
        return(NULL);
    }
    memset(table->elements, 0, size * sizeof(void *));

    table->size = size;
    return((hash_table_t)table);
}


/******************************************************************************
 * destroy_hash_table:
 *   Destroys a hash table.
 */
void destroy_hash_table(hash_table_t table)
{
    struct open_hash_table_t *tab = table;
    struct open_hash_element_t *e, **eh;
    int i;
    int num_killed = 0;

    /* Free any entries left in table. */
    for ( eh = tab->elements; (eh - tab->elements) < tab->size; eh++ )
    {
        e = *eh;
        while ( e != NULL )
        {
            struct open_hash_element_t *t = e->next_in_bucket;
            free(e);
            e = t;
        }
    }

    /* Free the bucket list, and the table itself. */
    free(tab->elements);
    free(tab);
}


/******************************************************************************
 * insert_hash_entry:
 *   Insert new entry into hash table.
 *   NOTE -- we do not check for duplicate entries!!!
 */
int insert_hash_entry(hash_table_t table, hash_key_t key, hash_entry_t entry)
{
    int                         index;
    struct open_hash_element_t  *new_el;
    struct open_hash_element_t  *cur_element;
    struct open_hash_table_t    *tab = (struct open_hash_table_t *)table;
    index = hash(tab, key);

    if ( (new_el = malloc(sizeof(struct open_hash_element_t))) == NULL )
    {
        /* Could not allocate new hash entry. */
	return(0);
    }
    else
    {
        /* Okay -- we can safely insert the new entry. */
        new_el->next_in_bucket = tab->elements[index];
        new_el->entry          = entry;
        new_el->key            = key;
        tab->elements[index]   = new_el;
        return(1);
    }
}


/******************************************************************************
 * remove_hash_entry:
 *   Remove entry with given key from the table, checking for existence of
 *   entry!!
 */
int remove_hash_entry(hash_table_t table, hash_key_t key)
{
    int                         index;
    struct open_hash_element_t  *new_element;
    struct open_hash_element_t **cur_element;
    struct open_hash_table_t    *tab = (struct open_hash_table_t *)table;
    index = hash(tab, key);

    /*
     * We must lock the global poll mutex since the poll routines munge the
     * pcb structures without locking each individual pcb!
     */
#ifdef USE_PTH
    if ( pthread_mutex_lock(&(global_poll_mutex)) ) return(0);
#endif 

    /* Scan the bucket list for the key. */
    cur_element = &tab->elements[index];
    while ( *cur_element && (*cur_element)->key != key )
        cur_element = &(*cur_element)->next_in_bucket;

    if ( (*cur_element) && (*cur_element)->key == key )
    {
        /* We found the key, so nuke the entry. */
	new_element  = *cur_element;
	*cur_element = new_element->next_in_bucket;

	free(new_element);
        pthread_mutex_unlock(&global_poll_mutex);
	return(1);
    }
    else
    {
        /* The key wasn't in the table! */
        pthread_mutex_unlock(&global_poll_mutex);
	return(0);
    }
}


/******************************************************************************
 * element_for_key:
 *   Search hash table for entry with given key, returning NULL if not
 *   found.
 */
hash_entry_t element_for_key(hash_table_t table, hash_key_t key)
{
    int                         index;
    struct open_hash_element_t *cur_element;
    struct open_hash_table_t   *tab;

    tab   = (struct open_hash_table_t *)table;
    index = hash(tab, key);

    /* Search bucket list for entry with given key. */
    cur_element = tab->elements[index];
    while ( cur_element != NULL && cur_element->key != key )
        cur_element = cur_element->next_in_bucket;

    if ( cur_element != NULL && cur_element->key == key )
    {
        /* Found the entry, so return data field. */
	return(cur_element->entry);
    }
    else
    {
	return(NULL);
    }
}
